package swordoffer.offer41;

import java.util.ArrayList;

public class BinarySearch {
    class MedianFinder {
        private ArrayList<Integer> list;

        /**
         * initialize your data structure here.
         */
        public MedianFinder() {
            this.list = new ArrayList<>();
        }

        public void addNum(int num) {
            int left = 0;
            int right = list.size() - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (num <= list.get(mid)) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            if (list.size() == 0) {
                list.add(num);
            } else {
                int index = list.get(left) >= num ? left : left + 1;
                list.add(index, num);
            }
        }

        public double findMedian() {
            int size = list.size();
            if ((size & 1) == 0) {
                return (list.get(size / 2) + list.get((size / 2) - 1)) / 2.0;
            } else {
                return (double) list.get(size / 2);
            }
        }
    }
}
